//////////////////////////////////////////////////////////////////////////
// Daniel Selnick
// Tim Lake
// CPSC 335 M/W - Analysis and Design of Algorithms
// 5/16/11
//////////////////////////////////////////////////////////////////////////
// includes
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <string>
#include "project1.h"
#include "project2.h"
#include "project3.h"
#include "project4.h"
#include "project5.h"
using namespace std;
// defines
#define MINARRAYSIZE 0
#define MAXARRAYSIZE 268400000
// forward function declaration
// global data
// main
 int __cdecl main()
{     
    char input;
    int size;
    do
    {
        // get user input
        cout << "Enter: " << endl;
        cout << "(b) for bubble sort, (s) for selection sort, (r) for reverse array" << endl;
        cout << "(m) for merge sort, (o) for optimized merge sort" << endl;
        cout << "(k) for knapsack" << endl;
        cout << "(d) for dynamic knapsack" << endl;
		cout << "(5) for vertex cover" << endl;
        cin >> input;
        cout << "Enter the length of data." << endl;
        //cin >> size;
        //size = clamp<int>(size, MINARRAYSIZE, MAXARRAYSIZE);       
        // initialize input for algorithm
        int * data;
        long testResult = 0;
        // run algorithm
        switch (input)
        {
        case 'b':
            {
                data = CreateData(size);
			    testResult = BubbleSort(data, size);
                delete data;
            }
        	break;
        case 's':
            {
                data = CreateData(size);
			    testResult = SelectionSort(data, size);
                delete data;
            }
            break;
        case 'r':
            {
                data = CreateData(size);
                testResult = ReverseArray(data, size);      
                delete data;
            }
            break;
        case 'm':
            {
                data = CreateData(size);
                testResult = clock();
                BaselineMergeSort(data, size);
                testResult = clock() - testResult;
                delete data;
            }
            break;
        case 'n':
            {
                data = CreateData(size);
                testResult = clock();
                OptMergeSort(*data, size - 1);
                testResult = clock() - testResult;
                delete data;
            }
            break;
        case 'k':
            {
                cout << "Enter maximum weight" << endl;
                int max;            
                cin >> max;            
                Package * packages = getPackages("packages.txt", size);
			    testResult = clock();
			    SET set = ExhaustiveKnapsack(packages, size, max);
			    testResult = clock() - testResult;
                PrintSet(set);
			    
                //displayPackages(packages, max);
                delete packages;
            }
            break;
        case 'd':
            {   
                nthousand();
                /*
				Package * packages = getPackages("packages.txt", 200);    
                int n =0;
                int w = 0;
                int * weight = new int[200];
                int * values = new int[200];
				list<int> knapResult;
                SET knapSet;
                /*
                // run time comparison between exhaustive and dynamic
                n = 20;
                w = 1000;

                cout << "Exhaustive n = 20, w = 1000" << endl;
                testResult = clock();
                knapSet = ExhaustiveKnapsack(packages, n, w);
                testResult = clock() - testResult;
                PrintSet(knapSet);
                cout << "Run-time: " << testResult << endl;
                long exhaustiveTime = testResult;

                cout << "Dynamic n = 20, w = 1000" << endl;
                convertPackages(packages, weight, values, n);
                testResult = clock();
                knapResult = DynamicKnapsack(weight, values, n, w);
                testResult = clock() - testResult;
                knapSet.clear();
                knapSet = CreateSet(packages, knapResult);
                PrintSet(knapSet);
                cout << "Run-time: " << testResult << endl;

                cout << "Time difference between exhaustive and dynamic: " << (exhaustiveTime - testResult) << endl;

                cout << "Largest value n with w = 2000" << endl;
                w = 2000;
                n = 1;
                testResult = 0;
                while (testResult <= 600000)
                {
                    n++;
                    knapSet.clear();
                    cout << endl << "Exhaustive Knapsack: " << endl << "n = " << n << "w = " << w << endl;
                    testResult = clock();
                    knapSet = ExhaustiveKnapsack(packages, n, w);
                    testResult = clock() - testResult;
                    PrintSet(knapSet);
                    cout << "Run-time: " << testResult << endl;
                }
                // the test after the one that's under 10 minutes shouldn't be counted as part of the n
                n--;

                cout << "Largest value n for run time of 10 minutes is: " << n << endl;

                cout << "Dynamic n = " << n <<  "w = 2000" << endl;
                exhaustiveTime = testResult;
                w = 2000;
                convertPackages(packages, weight, values, n);
                testResult = clock();
                knapResult = DynamicKnapsack(weight, values, n, w);
                testResult = clock() - testResult;
                knapSet.clear();
                knapSet = CreateSet(packages, knapResult);
                PrintSet(knapSet);
                cout << "Run-time: " << testResult << endl;

                cout << "Time difference between exhaustive and dynamic: " << (exhaustiveTime - testResult) << endl;

                // Run through all the tests for different media types
                MediaTests();
                 
                delete weight;
                delete values;
                delete packages;

                n = 1000;
                w = 1000;*/               
                               
            }
        case '5':
            {
                Graph graph = loadGraph();
				cout << "Loaded graph from 'swa.txt'\n" << "Got " << graph.NumVertices() << " vertices and " << graph.NumEdges() << " edges\n";
				RunVertexCoverTest(graph, 10);
                //RunVertexCoverTest(graph, 20);
                //RunVertexCoverTest(graph, 25);
                //RunVertexCoverTest(graph, 72);
                break;
            }
        }      
        // display output
        cout << "Test Result is: " << testResult << "milliseconds" << endl;
        // loop through process for multiple tests
        cout << "Try again? (y/n)" << endl;
        input = 0;
        cin >> input;
        if (input == 'n')
            input = 0;     
    } while(input); 
}

